package com.undone;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-12-03 19:02
 * @version: 1.0
 * @description: 1997 题 访问完所有房间的第一天
 * dp[i][0] = dp[i-1][1]+1，解释：每个房间访问的第1天，肯定是上一个房间第2次访问的日期+1
 * dp[i][1] = 2 * dp[i][0] - dp[nextVisit[i]][0] 解释：每个房间访问的第2天，是第1次访问的日期+第1次访问和第2次访问的间隔天数

 **/
public class FirstDayBeenInAllRooms {
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        //dp[i][0]表示奇数次到达i时需要的天数
        //dp[i][1]表示偶数次到达i时需要的天数
        long[][] dp = new long[nextVisit.length][2];
        dp[0][1] = 1;//第二次到达0时需要一天
        int mod = 1000000007;
        for (int i = 1; i < nextVisit.length; i++) {
            //第一次到达i时,得到达两次 i-1, 才能达到i
            dp[i][0] = (dp[i - 1][1] + 1) % mod;
            // 第二次到达i是在第一次的基础上 +1
            // 到达奇数次dp[nextVisit[i]][0],此时想要再次到达i,需要先偶数次的到达i-1
            // + (dp[i - 1][1] - dp[nextVisit[i]][0]),再次到达i-1需要的天数
            //再 +1 第二次到达i
            //                              注意:这里相减可能会出现负数,所以加上mod
            // (mod + dp[i - 1][1] - dp[nextVisit[i]][0])
            dp[i][1] = (dp[i][0] + 1 + (mod + dp[i - 1][1] - dp[nextVisit[i]][0]) + 1) % mod;
        }
        return (int) dp[dp.length - 1][0];
    }

}
